UVa/11367 - Full tank?/11367.2.cpp

   1 /*
   2   Time limit exceeded + Wrong answer!
   3  */
   4 #include <iostream>
   5 #include <vector>
   6 #include <queue>
   7 //#include <cassert>
   8
   9 using namespace std;
  10
  11 const int MAXN = 1000, MAXC = 100;
  12
  13 struct edge{
  14   int i, g, w;
  15   edge(){}
  16   edge(int I, int G, int W) : i(I), g(G), w(W) {}
  17   bool operator < (const edge &that) const {
  18     return w > that.w;
  19   }
  20 };
  21
  22
  23 int p[MAXN], //Prices
  24   d[MAXN][MAXC+1],
  25   n,
  26   mind[MAXN][MAXN]; //mind[i][j] = Min distance from node i to j
  27
  28 vector<edge> g[MAXN];
  29
  30 int min_distance(const int &start, const int &end){
  31   if (mind[start][end] == -1){
  32     vector<int> d(n, INT_MAX);
  33     d[start] = 0;
  34     priority_queue<edge> q;
  35     q.push(edge(start, 0, 0));
  36     while (q.size()){
  37       edge u = q.top();
  38       q.pop();
  39       if (u.i == end){
  40         mind[start][end] = u.w;
  41         break;
  42       }
  43       if (d[u.i] < u.w) continue;
  44       vector<edge> &v = g[u.i];
  45       for (int j=0; j<v.size(); ++j){
  46         int distance = v[j].w;
  47         int neighbor = v[j].i;
  48         if (u.w + distance < d[neighbor]){
  49           d[neighbor] = u.w + distance;
  50           q.push(edge(neighbor, 0, d[neighbor]));
  51         }
  52       }
  53     }
  54   }
  55   return mind[start][end];
  56 }
  57
  58
  59
  60 int dijkstra(const int &start, const int &end, const int &c){
  61   for (int i=0; i<n; ++i)
  62     for (int j=0; j<=c; ++j)
  63       d[i][j] = INT_MAX;
  64
  65   priority_queue<edge> q;
  66   q.push(edge(start, 0, 0));
  67   d[start][0] = 0;
  68
  69   while (q.size()){
  70     edge u = q.top();
  71     q.pop();
  72
  73     //printf("popped <%d, %d, %d>\n", u.i, u.g, u.w);
  74     if (u.i == end){
  75       return u.w;
  76     }
  77     if (d[u.i][u.g] < u.w) continue;
  78
  79     vector<edge> &v = g[u.i];
  80     for (int j=0; j<v.size(); ++j){
  81       int distance = v[j].w;
  82       int neighbor = v[j].i;
  83
  84       //no comprar nada
  85       if (u.g >= distance){
  86         int new_gas = u.g - distance;
  87         if (u.w < d[neighbor][new_gas]){
  88           d[neighbor][new_gas] = u.w;
  89           q.push(edge(neighbor, new_gas, u.w));
  90         }
  91       }
  92
  93       //comprar lo justito para llegar allá
  94       if (u.g < distance){
  95         int k = distance - u.g;
  96         if ( u.g + k <= c ){ //No puedo exceder el tanque
  97           int w_extra = k*p[u.i];
  98           if (u.w + w_extra < d[neighbor][0]){
  99             d[neighbor][0] = u.w + w_extra;
 100             q.push(edge(neighbor, 0, u.w + w_extra));
 101           }
 102         }
 103       }
 104
 105       //llenar el tanque
 106       if ( distance <= c ){
 107         int k = std::min(c, min_distance(neighbor, end)) - u.g;
 108         if (0 <= k && u.g + k <= c){ //no tengo más gasolina de la que necesito
 109           int w_extra = k*p[u.i];
 110           int new_gas = u.g - distance + k;
 111           if (u.w + w_extra < d[neighbor][new_gas]){
 112             d[neighbor][new_gas] = u.w + w_extra;
 113             q.push(edge(neighbor, new_gas, u.w + w_extra));
 114           }
 115         }
 116       }
 117
 118
 119       /*      for (int k = distance - u.g; k <= c + distance - u.g; ++k){
 120         int new_gas = u.g - distance + k;
 121         if (k >= 0 && 0 <= new_gas && u.g + k <= c ){
 122           int w_extra = k*p[u.i];
 123           //assert(w_extra >= 0);
 124           if (u.w + w_extra < d[neighbor][new_gas]){
 125             d[neighbor][new_gas] = u.w + w_extra;
 126             q.push(edge(neighbor, new_gas, u.w + w_extra));
 127             //printf("  pushed <%d, %d, %d>\n", neighbor, new_gas, u.w + w_extra);
 128           }
 129         }
 130         }*/
 131
 132     }
 133   }
 134   return INT_MAX;
 135
 136 }
 137
 138 int main(){
 139   int m;
 140   scanf("%d %d", &n, &m);
 141   for (int i=0; i<n; ++i){
 142     scanf("%d", &p[i]);
 143     for (int j=0; j<n; ++j){
 144       mind[i][j] = -1;
 145     }
 146     mind[i][i] = 0;
 147   }
 148
 149   while (m--){
 150     int u, v, d;
 151     scanf("%d %d %d", &u, &v, &d);
 152     g[u].push_back(edge(v, 0, d));
 153     g[v].push_back(edge(u, 0, d));
 154   }
 155
 156   int q;
 157   scanf("%d", &q);
 158   while (q--){
 159     int c, s, e;
 160     scanf("%d %d %d", &c, &s, &e);
 161     int t = dijkstra(s, e, c);
 162     if (t < INT_MAX){
 163       printf("%d\n", t);
 164     }else{
 165       printf("impossible\n");
 166     }
 167   }
 168   return 0;
 169 }